package com.oscorll.algorithm;

/**
 * 判断一个坐标是否在多边形内部
 */
public class PNPoly {

    public static void main(String[] args) {
        Point p1 = new Point(0, 0);
        Point p2 = new Point(0, 1);
        Point p3 = new Point(1, 1);
        Point p4 = new Point(1, 0);
        Point[] points = new Point[]{p1, p2, p3, p4};

        Point tp = new Point(1.5f, 0.5f);
        System.out.println(check(points, tp));
    }

    /**
     * PNPoly（Point in polygon）算法：任一射线穿过多边形，奇数段位于多边形之内，偶数段位于多边形之外
     *
     * 如何判定一点是否在给定顶点的不规则封闭区域内? - Milo Yip的回答 - 知乎
     * https://www.zhihu.com/question/26551754/answer/33185339
     *
     * @param points 多边形坐标
     * @param tp     需要判断的坐标
     * @return boolean 是否在多边形内部
     */
    public static boolean check(Point[] points, Point tp) {
        int length = 0;   // 多边形顶点个数
        boolean flag = false;   // 交点奇偶判断
        Point sp, ep;   // 多边形边的起始点

        if (points != null) {
            length = points.length;
        }
        for (int i = 0, j = length - 1; i < length; j = i++) {
            sp = points[i];
            ep = points[j];

            if (((sp.y > tp.y) != (ep.y > tp.y)) &&
                    (tp.x < (ep.x - sp.x) * (tp.y - sp.y) / (ep.y - sp.y) + sp.x)) {
                flag = !flag;
            }
        }

        return flag;
    }

}

class Point {
    float x;
    float y;

    Point(float x, float y) {
        this.x = x;
        this.y = y;
    }

}
